package leetcode_top;
import java.util.*;
import java.util.stream.Collectors;

import org.junit.Test;
public class Ex212 {
    class Solution1 {
        boolean[][] flag;
        int m, n;
        char[][] board;
        Map<Character, Set<String>> map;
        List<String> res;
        public List<String> findWords(char[][] board, String[] words) {
            m = board.length;
            n = board[0].length;
            flag = new boolean[m][n];
            map = new HashMap<>();
            res = new ArrayList<>();
            this.board = board;
            for (String s: words) {
                char c = s.charAt(0);
                if (map.containsKey(c)) {
                    map.get(c).add(s);
                } else {
                    Set<String> set = new HashSet<>();
                    set.add(s);
                    map.put(c, set);
                }
            }

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (map.containsKey(board[i][j])) {
                        Set<String> set  = map.get(board[i][j]);
                        for (String s: set) {
                            dfs(i, j, 0, s);
                        }
                    }
                }
            }
            return res.stream().distinct().collect(Collectors.toList());
        }

        public void dfs(int i, int j, int idx, String s) {
            if (i < 0 || i >= m || j < 0 || j >= n || flag[i][j] || s.charAt(idx) != board[i][j]) return;
            if (idx == s.length() - 1) {
                res.add(s);
                return;
            }
            flag[i][j] = true;
            dfs(i + 1, j, idx + 1, s);
            dfs(i - 1, j, idx + 1, s);
            dfs(i, j + 1, idx + 1, s);
            dfs(i, j - 1, idx + 1, s);
            flag[i][j] = false;
        }
    }

    /* 
        [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
        ["oath","pea","eat","rain","hklf", "hf"]
        输出：
        ["oath","eat","hklf"]
        预期结果：
        ["oath","eat","hklf","hf"]
    
    */

    //TODO 前缀树实现
    /* 
        主体仍然使用回溯。

        Solution1的回溯实现中，需要一个hashMap记录词典拥有的首字母单词，但是对于次字母就不友好，需要一次k规模的遍历
        使用前缀树避免遍历的行为。
        1. 编写前缀树类；
        2. 将words中内容嵌入前缀树；
        3. 将前缀树作为一个“字典”作为回溯的判断条件
        如何一次将具有相同前缀的所有单词不重复的全部拿出【树形动态规划】
    */
    class Solution {
        boolean[][] flag;
        int m, n;
        char[][] board;
        public List<String> findWords(char[][] board, String[] words) {
            m = board.length;
            n = board[0].length;
            this.board = board;
            flag = new boolean[m][n];
            res = new ArrayList<>();
            TireTree tt = new TireTree();
            for (int i = 0; i < words.length; i++) {
                tt.insert(words[i]);
            }
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    dfs(i, j, tt.root, "");
                }
            }
            return res;
        }

        List<String> res;
        /* 
            返回整形的目的是减去当前前缀树节点的count值
            为什么不每次-1？不能保证这条路径只走一次

            比如说测试用例：        
            char[][] cs = {new char[]{'o','a','a','n'},new char[]{'e','t','a','e'},new char[]{'i','h','k','r'},new char[]{'i','f','l','v'}};
            String[] words = {"oath","pea","eat","rain","hklf", "hf"};
            hklf和hk会在h->k这个路径上走两次，h和k的count应该减去2
            而采用每次-1 h和k只能减去1，因为只会走一次【缺少底层的没有停止脚步的信息】
        */
        public int dfs(int i, int j, Node pre, String s) {
            if (i < 0 || i >= m || j < 0 || j >= n || flag[i][j]) return 0;
            char c = board[i][j];

            Node cur = pre.next[c - 'a'];
            //这句话就是代表前一种方法的s.char(idx) != board[i][j]
            if (cur == null) return 0; //无词汇
            //判重
            if (cur.count == 0) return 0; //虽然有词汇，但是这个词汇之前已经加过了

            s += board[i][j]; //单词加上一个有效字符
            int cnt = 0; //这条分支所能产生的结果数量
            // cur.count--; //最后统一减去《注释分析》
            if (cur.end > 0) { //当前位置为一个词典单词结束位置，且未加过
                cur.end--;
                res.add(s);
                cnt++;
                // return 1; //此处并不return，因为可能还有更长的单词
            }
            flag[i][j] = true;

            cnt += dfs(i + 1, j, cur, s);
            cnt += dfs(i, j + 1, cur, s);
            cnt += dfs(i - 1, j, cur, s);
            cnt += dfs(i, j - 1, cur, s);

            cur.count -= (cnt);
            flag[i][j] = false;
            return cnt; //还要帮助上层节点减去路径
        }

        class TireTree {
            Node root;
            public TireTree() {
                this.root = new Node();
            }

            public void insert(String s) {
                char[] cs = s.toCharArray();
                char c;
                Node p = root, n;
                for (int i = 0; i < cs.length; i++) {
                    c = cs[i];
                    n = p.next[c - 'a'];
                    if (n == null) {
                        n = new Node();
                        p.next[c - 'a'] = n;
                    }
                    n.count++;
                    p = n;
                }
                p.end++;
            }
        }

        class Node {
            Node[] next;
            int end;
            int count;

            public Node() {
                this.next = new Node[26];
            }
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        char[][] cs = {new char[]{'o','a','a','n'},new char[]{'e','t','a','e'},new char[]{'i','h','k','r'},new char[]{'i','f','l','v'}};
        String[] words = {"oath","pea","eat","rain","hklf", "hf"};
        System.out.println(s.findWords(cs, words));
    }
}